Hadwiger Number
   HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Hadwiger number of an
undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
is the size of the largest
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
that can be obtained by contracting edges of . Equivalently, the Hadwiger number is the largest number for which the complete graph is a
minor Minor may refer to: Common meanings * Minor (law), a person not under the age of certain legal activities. * Academic minor, a secondary field of study in undergraduate education Mathematics * Minor (graph theory), a relation of one graph to an ...
of , a smaller graph obtained from by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of or the homomorphism degree of . It is named after
Hugo Hadwiger Hugo Hadwiger (23 December 1908 in Karlsruhe, Germany – 29 October 1981 in Bern, Switzerland) was a Swiss people, Swiss mathematician, known for his work in geometry, combinatorics, and cryptography. Biography Although born in Karlsruhe, Ge ...
, who introduced it in 1943 in conjunction with the
Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...
, which states that the Hadwiger number is always at least as large as the
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
of . The graphs that have Hadwiger number at most four have been characterized by . The graphs with any finite bound on the Hadwiger number are sparse, and have small chromatic number. Determining the Hadwiger number of a graph is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
but
fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
.


Graphs with small Hadwiger number

A graph has Hadwiger number at most two
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it is a
forest A forest is an ecosystem characterized by a dense ecological community, community of trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, ...
, for a three-vertex complete minor can only be formed by contracting a
cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in ...
in . A graph has Hadwiger number at most three if and only if its
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests ...
is at most two, which is true if and only if each of its
biconnected component In graph theory, a biconnected component or block (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. Th ...
s is a
series–parallel graph In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and t ...
.
Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its graph minor, minors include neither ''K''5 (the complete g ...
, which characterizes the
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s by their
forbidden minors Forbidden may refer to: Science * Forbidden mechanism, a spectral line associated with absorption or emission of photons Films * ''Forbidden'' (1919 film), directed by Phillips Smalley and Lois Weber * ''Forbidden'' (1932 film), directed by Fra ...
, implies that the planar graphs have Hadwiger number at most four. In the same paper that proved this theorem, also characterized the graphs with Hadwiger number at most four more precisely: they are graphs that can be formed by
clique-sum In graph theory, a branch of mathematics, a clique sum (or clique-sum) is a way of combining two graphs by gluing them together at a clique (graph theory), clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' ...
operations that combine planar graphs with the eight-vertex
Wagner graph In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph. Properties As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, ...
. The graphs with Hadwiger number at most five include the
apex graph In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is ''an'' apex, not ''the'' apex because an apex graph may have ...
s and the linklessly embeddable graphs, both of which have the complete graph among their forbidden minors.


Sparsity

Every graph with vertices and Hadwiger number has edges. This bound is tight: for every , there exist graphs with Hadwiger number that have edges.; . The letters O and Ω in these expressions invoke
big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
.
If a graph has Hadwiger number , then all of its subgraphs also have Hadwiger number at most , and it follows that must have degeneracy . Therefore, the graphs with bounded Hadwiger number are
sparse graph In mathematics, a dense graph is a Graph (discrete mathematics), graph in which the number of edges is close to the maximal number of edges (where every pair of Vertex (graph theory), vertices is connected by one edge). The opposite, a graph with ...
s.


Coloring

The
Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...
states that the Hadwiger number is always at least as large as the
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
of . That is, every graph with Hadwiger number should have a
graph coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
with at most colors. The case is equivalent (by Wagner's characterization of the graphs with this Hadwiger number) to the
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...
on colorings of
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, and the conjecture has also been proven for , but remains unproven for larger values of . Because of their low degeneracy, the graphs with Hadwiger number at most can be colored by a
greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...
algorithm using colors.


Computational complexity

Testing whether the Hadwiger number of a given graph is at least a given value is
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
, from which it follows that determining the Hadwiger number is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
. However, the problem is
fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
: there is an algorithm for finding the largest clique minor in an amount of time that depends only polynomially on the size of the graph, but exponentially in . Additionally, polynomial time algorithms can approximate the Hadwiger number significantly more accurately than the best polynomial-time approximation (assuming P ≠ NP) to the size of the largest complete subgraph.


Related concepts

The
achromatic number In graph theory, a complete coloring is a (proper) vertex coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such ...
of a graph is the size of the largest clique that can be formed by contracting a family of independent sets in .
Uncountable In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger tha ...
clique minors in infinite graphs may be characterized in terms of havens, which formalize the evasion strategies for certain
pursuit–evasion Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early ...
games: if the Hadwiger number is uncountable, then it equals the largest order of a haven in the graph. Every graph with Hadwiger number has at most
cliques A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...
(complete subgraphs). defines a class of graph parameters that he calls -functions, which include the Hadwiger number. These functions from graphs to integers are required to be zero on graphs with no edges, to be minor-monotone, to increase by one when a new vertex is added that is adjacent to all previous vertices, and to take the larger value from the two subgraphs on either side of a
clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
separator. The set of all such functions forms a
complete lattice In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum ( join) and an infimum ( meet). A conditionally complete lattice satisfies at least one of these properties for bounded subsets. For compariso ...
under the operations of elementwise minimization and maximization. The bottom element in this lattice is the Hadwiger number, and the top element is the
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests ...
.


Footnotes


Notes


References

*. *. *. *. *. *. *. *. *. *. *. *. {{refend Graph invariants Graph minor theory NP-complete problems